package likou;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class _312 {
    public static void main(String[] args) {
        Set<Integer> set = new HashSet<>();
        set.add(1);
        set.add(2);
        set.add(4);
        set.add(5);
        set.add(3);
        for (int i:set){
            System.out.println(i);
        }
//        _312 one = new _312();
//        System.out.println(one.maxCoins(new int[]{3, 1, 5, 8}));
    }
    public int maxCoins(int[] nums){
        int n = nums.length;
        int[][] dp = new int[n][n];
        for(int i=0;i<n;i++){
            dp[i][i] = nums[i]*this.lr(nums,i-1,i+1);
        }
        for (int l=n-1;l>=0;l--){
            for (int r=l+1;r<n;r++){
                int lr = this.lr(nums,l-1,r+1);
                int max = dp[l+1][r]+nums[l]*lr;
                max = Math.max(max,dp[l][r-1]+nums[r]*lr);
                System.out.println("1："+max+" "+dp[l][r-1]+" "+nums[r]+" "+lr+" "+l+" "+r);
                System.out.println(Arrays.toString(nums));
                for(int i=l+1;i<r;i++){
                    max = Math.max(max,dp[l][i-1]+dp[i+1][r]+nums[i]*lr);
                    System.out.println("2："+max+" "+dp[l][i-1]+" "+dp[i+1][r]+" "+nums[i]*lr);
                }
                dp[l][r] = max;
                for (int[] dps :dp){
                    System.out.println(Arrays.toString(dps));
                }
                System.out.println();
            }
        }
        return dp[0][n-1];
    }
    private int lr(int[] nums ,int l,int r){
        int lnum = l==-1?1:nums[l];
        int rnum = r==nums.length?1:nums[r];
        return lnum*rnum;
    }
}
